package com.company.tree;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class TargetCopy {


    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        //由原始树获取路径
        Stack<String> originalPath = getOriginalPath(original, target);
        TreeNode treeNode = throuthPath(cloned, originalPath);
        return treeNode;
    }

    private Stack<String> getOriginalPath(final TreeNode originalTree, final TreeNode target) {
        Stack<String> paths = new Stack<>();

        canReachTheTarget(originalTree, target, paths);
        return paths;
    }

    private boolean canReachTheTarget(final TreeNode root, TreeNode target, Stack<String> path) {
        if (root == target) {
            path.push("target");
            return true;
        }
        boolean reached = false;
        if (root.left != null) {
            reached = canReachTheTarget(root.left, target, path);
            if (reached) {
                path.push("left");
                return true;
            }
        }


        if (root.right != null) {

            reached = canReachTheTarget(root.right, target, path);
            if (reached) {
                path.push("right");
                return true;
            }
        }
        return false;
    }

    private TreeNode throuthPath(final TreeNode clonedTree, Stack<String> paths) {
        if (paths.isEmpty()) {
            return null;
        }
        TreeNode node = clonedTree;
        while (!paths.isEmpty()) {
            switch (paths.pop()) {
                case "target":
                    return node;
                case "left":
                    node = node.left;
                    break;
                case "right":
                    node = node.right;
                    break;
            }
        }
        return node;
    }
}
